class Solution {
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};
    int m = 0, n = 0;
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size(), n = matrix[0].size();
        int ret = 0;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                ret = max(ret, dfs(i, j, matrix));
            }
        }
        return ret + 1; // 加上自己
    }
 
    int dfs(int sr, int sc, vector<vector<int>>& matrix)
    {
        int ret = 0;
        for(int i = 0; i < 4; ++i)
        {
            int x = sr + dx[i], y = sc + dy[i];
            if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[sr][sc])
            {
                ret = max(ret, dfs(x, y, matrix) + 1);
            }
        }
        return ret;
    }
};